package 牛客剑指专题二刷.二叉树;

/**
 * author:JiangSong
 * Date:2023/7/3
 **/

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 按之字形顺序打印二叉树
 法1：二叉树层序遍历
 */

public class JZ77 {
     public class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;
   public TreeNode(int val) {
     this.val = val;
   }
 }
    public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
        // write code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(pRoot == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);
        boolean flag = true;
        while(!queue.isEmpty()){
            int n = queue.size();
            ArrayList<Integer> tmp = new ArrayList<>();
            for(int i = 0; i < n; ++i){

                TreeNode node = queue.poll();
                if(flag){
                    tmp.add(node.val);
                }else{
                    tmp.add(0,node.val);
                }
                if(node.left != null)queue.offer(node.left);
                if(node.right != null)queue.offer(node.right);
            }
            flag = !flag;
            res.add(tmp);
        }
        return res;
    }
}
